//给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
//
//
// 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
//
//
// 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
//
// 以这种方式修改数组后，返回数组 可能的最大和 。
//
//
//
// 示例 1：
//
//
//输入：nums = [4,2,3], k = 1
//输出：5
//解释：选择下标 1 ，nums 变为 [4,-2,3] 。
//
//
// 示例 2：
//
//
//输入：nums = [3,-1,0,2], k = 3
//输出：6
//解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。
//
//
// 示例 3：
//
//
//输入：nums = [2,-3,-1,5,-4], k = 2
//输出：13
//解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 10⁴
// -100 <= nums[i] <= 100
// 1 <= k <= 10⁴
//
// Related Topics 贪心 数组 排序 👍 139 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        // 暴力
//        while (k != 0) {
//            Arrays.sort(nums);
//            nums[0] = -nums[0];
//            k--;
//        }
//
//        int res = 0;
//        for (int num : nums) {
//            res += num;
//        }
//        return res;

        // 桶排序
        // nums[i]的范围是-100~100，申请个201的正好够用
        int[] arr = new int[201];
        for (int num : nums) {
            // 把所有数字往前移100，防止负数的索引
            arr[num + 100]++;
        }

        // 遍历前100个数，也就是原负数的部分
        for (int i = 0; i < 100; i++) {
            if (arr[i] != 0) {
                // 取数量与k的最小值
                int count = Math.min(k, arr[i]);
                // 负数的部分减去相应的数量
                arr[i] -= count;
                // 负数的相反数加上相应的数量
                // 原负数为：i-100，取反为： -(i-100)，再加上偏移量为：-(i-100)+100=-i+200
                arr[-i + 200] += count;
                // k也减去相应的数量
                k -= count;
                // k减到0的，跳出循环
                if (k == 0) {
                    break;
                }
            }
        }

        // 如果 k 还有剩余且为奇数，取最小的正数（或零）变换一次
        if (k % 2 != 0) {
            // 从100开始，也就是从原来的0开始
            for (int i = 100; i < 201; i++) {
                if (arr[i] != 0) {
                    // 减一次
                    arr[i]--;
                    // 对应的负数加一次
                    // 原正数为：i-100，取反为：-(i-100)，再加上偏移量为：-(i-100)+100=-i+200
                    arr[-i + 200]++;
                    break;
                }
            }
        }

        // 统计结果
        int ans = 0;
        for (int i = 0; i < 201; i++) {
            ans += arr[i] * (i - 100);
        }

        return ans;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
